class Solution:
    def findMedianSortedArrays(self, nums1, nums2):
        if len(nums1) > len(nums2):
            nums1, nums2 = nums2, nums1 # swap减少二分查找次数,把nums1 设置为较短的数列
            
        m, n = len(nums1), len(nums2)
        mark = (m+n-1) // 2 # 总长度切半,half_len
        l, r = 0, m # nums1的左右边界
        while l < r:
            mid = (l+r) // 2 # nums1 切半，取中间的位置值。
            if mark-mid-1 < 0 or nums1[mid] >= nums2[mark-mid-1]:
                # mark-mid-1；总长度切半 - nums1切半。
                # nums1[mid] nums1 的中间位 >= nums2[mark-mid-1] nums2
                r = mid
            else:
                l = mid + 1
        middlepoints = sorted(nums1[l:l+2] + nums2[mark-l:mark-l+2])
        return (middlepoints[0] + middlepoints[1-(m+n)%2]) / 2.0


if __name__ == '__main__':
    l1 = [1,2,3,4,5,6]
    l2 = [1,2,3,4,5,6,7,8,9]
    a = Solution()
    b = a.findMedianSortedArrays(l1, l2)
    print(b)